#define DEBUG
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int maxn=50000, maxq=50000;

class SegmentTree {
public:
  int v[4*maxn+1], tag[4*maxn+1], ans[4*maxn+1], left[4*maxn+1];

  void build(int o, int l, int r) {
    left[o] = l;
    ans[o] = v[o] = tag[o] = 0;
    if (l!=r) {
      int mid=(l+r)/2;
      build(o*2, l, mid);
      build(o*2+1, mid+1, r);
    }
  }

  void pushDown(int o, int l, int r) {
    if (tag[o]) {
      v[o] = max(v[o], tag[o]);
      ans[o] = max(ans[o], tag[o]-left[o]+1);
      if (l!=r) {
        tag[o*2] = max(tag[o*2], tag[o]);
        tag[o*2+1] = max(tag[o*2+1], tag[o]);
      }
      tag[o] = 0;
    }
  }

  void set(int o, int l, int r, int tl, int tr, int tv) {
    pushDown(o, l, r);
    if (l==tl && r==tr) {
      tag[o] = max(tag[o], tv);
      pushDown(o, l, r);
    } else {
      int mid=(l+r)/2;
      if (tl<=mid) {
        set(o*2, l, mid, tl, min(tr, mid), tv);
      } else {
        pushDown(o*2, l, mid);
      }
      if (tr>mid) {
        set(o*2+1, mid+1, r, max(tl, mid+1), tr, tv);
      } else {
        pushDown(o*2+1, mid+1, r);
      }
      v[o] = max(v[o*2], v[o*2+1]);
      ans[o] = max(ans[o*2], ans[o*2+1]);
    }
  }

  void dis(int o, int l, int r, int t) {
    pushDown(o, l, r);
    if (l==r) {
      left[o] = maxn+1;
      ans[o] = 0;
    } else {
      int mid=(l+r)/2;
      if (t<=mid) {
        dis(o*2, l, mid, t);
        pushDown(o*2+1, mid+1, r);
      } else {
        dis(o*2+1, mid+1, r, t);
        pushDown(o*2, l, mid);
      }
      left[o] = min(left[o*2], left[o*2+1]);
      ans[o] = max(ans[o*2], ans[o*2+1]);
    }
  }

  int get(int o, int l, int r, int tl, int tr) {
    pushDown(o, l, r);
    if (l==tl && r==tr) {
      return v[o];
    } else {
      int mid=(l+r)/2, ret=0;
      if (tl<=mid) {
        ret = max(ret, get(o*2, l, mid, tl, min(tr, mid)));
      }
      if (tr>mid) {
        ret = max(ret, get(o*2+1, mid+1, r, max(tl, mid+1), tr));
      }
      return ret;
    }
  }

  int getAns(int o, int l, int r, int tl, int tr) {
    pushDown(o, l, r);
    if (l==tl && r==tr) {
      return ans[o];
    } else {
      int mid=(l+r)/2, ret=0;
      if (tl<=mid) {
        ret = max(ret, getAns(o*2, l, mid, tl, min(tr, mid)));
      }
      if (tr>mid) {
        ret = max(ret, getAns(o*2+1, mid+1, r, max(tl, mid+1), tr));
      }
      return ret;
    }
  }
};

class Ele {
public:
  int k, v;

  static bool cmp(Ele &a, Ele &b) {
    return a.k<b.k;
  }
};

void solve(int n, int q, int a[], int que[][2], int ans[]) {
  static int l[maxn+1], r[maxn+1], sta[maxn+1];
  static Ele node[maxn+1], ques[maxq+1];

  sta[0] = 0;
  for (int i=1; i<=n; i++) {
    for (; sta[0] && a[i]>=a[sta[sta[0]]]; sta[0]--);
    l[i] = sta[0] ? sta[sta[0]]+1 : 1;
    sta[++sta[0]] = i;
  }
  sta[0] = 0;
  for (int i=n; i>0; i--) {
    for (; sta[0] && a[i]<=a[sta[sta[0]]]; sta[0]--);
    r[i] = sta[0] ? sta[sta[0]]-1 : n;
    sta[++sta[0]] = i;
  }

  for (int i=1; i<=n; i++) {
    node[i].k = r[i], node[i].v = i;
  }
  sort(node+1, node+n+1, Ele::cmp);
  for (int i=1; i<=q; i++) {
    ques[i].k = que[i][1], ques[i].v = i;
  }
  sort(ques+1, ques+q+1, Ele::cmp);

  static SegmentTree tot, size;
  tot.build(1, 1, n);
  size.build(1, 1, n);
  for (int i=1, j=1, k=1; i<=q; i++) {
    for (; j<=ques[i].k; j++) {
      for (; node[k].k<j; k++) {
        int x=node[k].v, len=tot.get(1, 1, n, x, x)-x+1;
        tot.dis(1, 1, n, x);
        size.set(1, 1, n, x, x, len);
      }

      tot.set(1, 1, n, l[j], j, j);
    }

    int x=ques[i].v;
    ans[x] = max(ans[x], max(size.get(1, 1, n, que[x][0], que[x][1]), tot.getAns(1, 1, n, que[x][0], que[x][1])));
  }
}

int main() {
#ifdef DEBUG
  freopen("src.in", "r", stdin);
  freopen("src.out", "w", stdout);
#endif

  static int a[maxn+1], que[maxq+1][2], ans[maxq+1];
  int n, q;
  scanf("%d", &n);
  for (int i=1; i<=n; i++) {
    scanf("%d", a+i);
  }
  scanf("%d", &q);
  for (int i=1; i<=q; i++) {
    scanf("%d %d", que[i], que[i]+1);
  }

  solve(n, q, a, que, ans);

  for (int i=1; i<=n/2; i++) {
    swap(a[i], a[n-i+1]);
  }
  for (int i=1; i<=q; i++) {
    int l=que[i][0], r=que[i][1];
    que[i][0] = n-r+1, que[i][1] = n-l+1;
  }
  solve(n, q, a, que, ans);

  for (int i=1; i<=q; i++) {
    printf("%d\n", ans[i]);
  }

  fclose(stdin);
  fclose(stdout);
  return 0;
}
